package common

import (
	"fmt"
)

type  TreeNode struct {
	Val  int
	Left, Right *TreeNode
}

func BuildTreeNode(nums []int) *TreeNode {
	var tree *TreeNode
	for _, num := range nums {
		if tree == nil {
			tree = &TreeNode{Val: num}
			continue
		}
		tree.Add(num)
	}
	return tree
}

func (t *TreeNode) Add(num int) {
	p := t
	for p != nil {
		if num < p.Val {
			if p.Left == nil {
				p.Left = &TreeNode{Val: num}
				break
			}
			p = p.Left
		} else if num > p.Val {
			if p.Right == nil {
				p.Right = &TreeNode{Val: num}
				break
			}
			p = p.Right
		} else {
			fmt.Println("duplicate number")
			break
		}
	}
}

func (t *TreeNode) MaxDepth() int {
	if t == nil {
		return 0
	}
	left := t.Left.MaxDepth()
	right := t.Right.MaxDepth()
	return Max(left, right) + 1
}

// DFS: 分为前序，中序，后序
// 前序遍历：根 -> 左子树 -> 右子树
func (t *TreeNode) PreOrder() []int {
	var preOrder func(p *TreeNode)
	var result []int
	preOrder = func(p *TreeNode) {
		if p != nil {
			result = append(result, p.Val)
			preOrder(p.Left)
			preOrder(p.Right)
		}
	}
	preOrder(t)
	return result
}

// 中序遍历: 左子树 -> 根 -> 右子树
func (t *TreeNode) InOrder() []int {
	var inOrder func(p *TreeNode)
	var result []int
	inOrder = func(p *TreeNode) {
		if p!=nil {
			inOrder(p.Left)
			result = append(result, p.Val)
			inOrder(p.Right)
		}
	}
	inOrder(t)
	return result
}

// 后序遍历：左子树 -> 右子树 -> 根
func (t *TreeNode) PostOrder() []int {
	var postOrder func(p *TreeNode)
	var result []int
	postOrder = func(p *TreeNode) {
		if p!= nil {
			postOrder(p.Left)
			postOrder(p.Right)
			result = append(result, p.Val)
		}
	}
	postOrder(t)
	return result
}

// DFS： 深度搜索（非递归）
// 需要用到栈
func DFS(r *TreeNode) []int {
	var result []int
	if r == nil {
		return result
	}
	var stack []*TreeNode
	stack = append(stack, r)
	size := len(stack)
	for len(stack) > 0 {
		p := stack[size-1] // 先进后出，取最后压栈数据
		stack = stack[:size-1]
		size--
		result = append(result, p.Val)
		// 先右
		if p.Right != nil {
			stack = append(stack, p.Right)
			size++
		}
		// 后左
		if p.Left != nil {
			stack = append(stack, p.Left)
			size++
		}
	}
	return result
}

// 广度搜索(层序遍历)
// 需要用到队列
func BFS(r *TreeNode) []int {
	var result []int
	if r == nil {
		return result
	}
	var queue []*TreeNode // 队列
	queue = append(queue, r)
	size := len(queue)
	for len(queue) > 0 {
		// pop
		p := queue[0]
		queue = queue[1:]
		size--
		result = append(result, p.Val)
		if p.Left != nil {
			queue = append(queue, p.Left)
			size++
		}
		if p.Right != nil {
			queue  =append(queue, p.Right)
			size++
		}
	}
	return result
}

func CreateUncertainTree(nums []int) *TreeNode {
	var t *TreeNode
	for _, n := range nums {
		if n == -1 {

		}

	}
	return t
}